//所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究
//非常有帮助。 
//
// 编写一个函数来查找目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。 
//
// 
//
// 示例： 
//
// 输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
//输出：["AAAAACCCCC", "CCCCCAAAAA"] 
// Related Topics 位运算 哈希表 
// 👍 118 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

import java.util.*;

/**
 * Java：重复的DNA序列
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P187_RepeatedDnaSequences {
    public static void main(String[] args) {
        Solution solution = new P187_RepeatedDnaSequences().new Solution();
        // TODO 此处开始你的表演
        MyUtil.print(solution.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> findRepeatedDnaSequences(String s) {
            // 字串长度
            int sl = 10;
            Set<String> set = new HashSet<>();
            if (s.length() < sl + 1) {
                return new ArrayList<>(set);
            }
            Map<String, Integer> map = new HashMap<>();
            for (int i = 0; i < s.length() - sl + 1; i++) {
                String subStr = s.substring(i, i + sl);
                if (map.get(subStr) == null) {
                    map.put(subStr, 1);
                } else {
                    set.add(subStr);
                }
            }
            return new ArrayList<>(set);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}